/**
//在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。 
//
// 
//
// 示例 1: 
//
// 输入: [7,5,6,4]
//输出: 5 
//
// 
//
// 限制： 
//
// 0 <= 数组长度 <= 50000 
// Related Topics 树状数组 线段树 数组 二分查找 分治 有序集合 归并排序 👍 730 👎 0

*/

package com.xixi.basicAlgroithms.sort;
public class ID_Offer_51_ShuZuZhongDeNiXuDuiLcof {
public static void main(String[] args) {
Solution solution = new ID_Offer_51_ShuZuZhongDeNiXuDuiLcof().new Solution();
}


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {


    public int result = 0;
    public int reversePairs(int[] nums) {
        if(nums.length > 1){
            mergeSort(nums,0, nums.length - 1);
        }

        return result;

    }


    public int[] mergeSort(int[] nums, int start, int end){
        if(start == end){
            return new int[]{nums[end]};
        }

        int nextPivot = start + (end - start)/2;

        int[] pre = mergeSort(nums, start,nextPivot);
        int[] tail = mergeSort(nums, nextPivot+1,end);


        //合并
        int[] mergeNum = new int[end - start + 1];
        int pIndex = 0;
        int tIndex = 0;
        int mergeIndex = 0;

        while(pIndex < pre.length && tIndex < tail.length){

            if(pre[pIndex] > tail[tIndex]){ //前数组大于后数组，则逆序度直接增加tail.length - tailIndex个
                result += ( tail.length - tIndex);
                mergeNum[mergeIndex] = pre[pIndex]; //返回得数组从大到小排序，确保后面的数字都小于当前index
                pIndex++;
            }else{
                mergeNum[mergeIndex] = tail[tIndex];
                tIndex++;
            }

            mergeIndex++;

        }

        while(pIndex < pre.length){
            mergeNum[mergeIndex] = pre[pIndex];
            pIndex++;
            mergeIndex++;
        }
        while(tIndex < tail.length){
            mergeNum[mergeIndex] = tail[tIndex];
            tIndex++;
            mergeIndex++;
        }

        return mergeNum;






    }

}
//leetcode submit region end(Prohibit modification and deletion)




}